package com.learn.tree.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * binary tree
 * @author LR2SD
 * @description
 * @date 2018-10-31 20:54
 */
public class BinaryTree<E extends Comparable<E>> {

    private TreeNode<E> root;

    private int size;



    public BinaryTree(){
        this.size=0;
        this.root=null;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }
    public TreeNode<E> getRoot(){
        return root;
    }

    public  void insert(E e){
        TreeNode<E> newNode=new TreeNode<E>(e);
        //root=insert(root,newNode);
        if(root==null){
            size++;
            root=newNode;
            return;
        }else{
            insert(root,newNode);
        }

    }
    //返回二分搜索树的根
    private void insert(TreeNode<E> rootNode, TreeNode<E> newNode) {



         if(((newNode.e).compareTo(rootNode.e)>0)&&rootNode.right==null){
             size++;
             rootNode.right=newNode;
             return;

        }else if(((newNode.e).compareTo(rootNode.e)<0)&&rootNode.left==null){
             size++;
             rootNode.left=newNode;
             return;

        }

        if((newNode.e).compareTo(rootNode.e)>0){

            insert(rootNode.right,newNode);

        }else if((newNode.e).compareTo(rootNode.e)<0){

            insert(rootNode.left,newNode);

        }


    }

    /**
     * 查询节点
     * @param e
     * @return
     */
    public TreeNode find(E e){

        return find(root,e);

    }

    private TreeNode find(TreeNode<E> node, E e) {
        if(node==null){
            return null;
        }
        if(node.e.equals(e)){
            return node;
        }else if(e.compareTo(node.e)<0){
            return find(node.left,e);
        }else{
            return find(node.right,e);
        }
    }



    //返回二分搜索树的根
//    private TreeNode<E> insert(TreeNode<E> rootNode, TreeNode<E> newNode){
//        if(rootNode==null){
//            size++;
//            return newNode;
//        }
//        if((newNode.e).compareTo(rootNode.e)>0){
//            rootNode.right=insert(rootNode.right,newNode);
//        }else if((newNode.e).compareTo(rootNode.e)<0){
//            rootNode.left= insert(rootNode.left,newNode);
//        }
//        return rootNode;
//    }

    /**
     * 前序遍历
     */
    public void preForEach(){
        preForEach(root);

    }
    private void preForEach(TreeNode node) {
        if (node == null) {
            return;
        }


        preForEach(node.left);

        preForEach(node.right);

    }

    /**
     * 中序遍历
     */
    public void midForEach(){
        midForEach(root);

    }
    private void midForEach(TreeNode node) {
        if (node == null) {
            return;
        }

        if (node.left != null) {

            midForEach(node.left);
            //System.out.println(node.left.e);
        }
        System.out.println(node.e);
        if (node.right != null) {
            midForEach(node.right);
            //System.out.println(node.right.e);
        }
    }

    /**
     * 后续遍历
     */
    public void postForEach(){
        postForEach(root);

    }
    private void postForEach(TreeNode node) {
        if (node == null) {
            return;
        }
        if (node.left != null) {

            postForEach(node.left);
            //System.out.println(node.left.e);
        }
        if (node.right != null) {
            postForEach(node.right);
            //System.out.println(node.right.e);
        }
        System.out.println(node.e);
    }


    /**
     * 广度优先遍历
     */
    public void levelForEach(){
        Queue<TreeNode<E>> queue=new LinkedList<TreeNode<E>>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode<E> node=queue.peek();
            if(node!=null){
                queue.add(node.left);
                queue.add(node.right);
                System.out.println(node.e);
            }

            queue.remove(node);
        }
    }

    /**
     * 得到最小元素对应的值
     * @return
     */
    public E minNode(){
        if(size==0){
            throw new IllegalArgumentException("bst is null");
        }
        return minNode(root).e;
    }

    private TreeNode<E> minNode(TreeNode node) {
        if(node.left==null){
            return node;
        }
        return minNode(node.left);
    }

    /**
     * 得到最大元素对应的值
     * @return
     */
    public E maxNode(){
        if(size==0){
            throw new IllegalArgumentException("bst is null");
        }
        return maxNode(root).e;
    }

    private TreeNode<E> maxNode(TreeNode node) {
        if(node.right==null){
            return node;
        }
        return minNode(node.right);
    }

    /**
     * 删除最小的节点，返回的节点对应的值
     * @return
     */
    public E removeMinNode(){
        E ret=minNode();
        root=removeMinNode(root);

        return ret;
    }

    /**
     * 删除node为根的最小节点，并返回删除后的心的根节点
     * @param node
     * @return
     */
    private TreeNode removeMinNode(TreeNode node) {
        if(node.left==null){
            TreeNode rightNode=node.right;
            node.right=null;
            size--;
            return rightNode;
        }
        node.left=removeMinNode(node.left);
        return node;
    }


    /**
     * 删除最小的节点，返回的节点对应的值
     * @return
     */
    public E removeMaxNode(){
        E ret=minNode();
        root=removeMaxNode(root);

        return ret;
    }

    /**
     * 删除node为根的最大节点，并返回删除后的新的根节点
     * @param node
     * @return
     */
    private TreeNode removeMaxNode(TreeNode node) {
        if(node.right==null){
            TreeNode rightNode=node.left;
            node.left=null;
            size--;
            return rightNode;
        }
        node.right=removeMinNode(node.right);
        return node;
    }

    /**
     * 删除元素
     * @param e
     * @return
     */
    public void remove(E e){

        root=remove(root,e);

    }

    /**
     * 删除元素，返回删除元素e之后的返回信的跟节点
     * @param node
     * @param e
     * @return
     */
    private TreeNode<E> remove(TreeNode<E> node, E e) {
        if(node==null){
            return null;
        }
        if(e.compareTo(node.e)<0){
            node.left=remove(node.left,e);
        }else if(e.compareTo(node.e)>0){
            node.right=remove(node.right,e);
        }else {
            if(node.left==null){//左节点为null
                TreeNode<E> rightNode=node.right;
                node.right=null;
                return rightNode;
            }else if(node.right==null){//右节点为null
                TreeNode<E> leftNode=node.left;
                node.left=null;
                return leftNode;
            }else{
                //获取左子树的最大节点--获取前驱节点
                TreeNode<E> processor=maxNode(node.left);
                processor.left=removeMaxNode(node.left);
                processor.right=node.right;
                node.left=node.right=null;
                return processor;
            }
        }

        return node;
    }


    /**
     * 寻找左边节点中最右边的
     * @param node
     * @return
     */
    private TreeNode getLeftMaxNode(TreeNode node){

        return node.right==null?node:getLeftMaxNode(node.right);
    }
    /**
     * 寻找右边节点中最左边的
     * @param node
     * @return
     */
    private TreeNode getRightMinNode(TreeNode node){

        return node.left==null?node:getRightMinNode(node.left);
    }

    public static void main(String [] args){
        BinaryTree<Integer> binaryTree=new BinaryTree<Integer>();
        int arr []={42,35,67,21,38,52,88,15,39,10,40,50,60};
        //int arr []={42};
        for(int i=0;i<arr.length;i++){
            binaryTree.insert(arr[i]);
        }
        //System.out.println(binaryTree.getSize());

        Integer a=35;

        TreeNode e=binaryTree.find(a);
        //System.out.println(e);

        //binaryTree.preForEach();

        //binaryTree.midForEach();

        //binaryTree.postForEach();

        binaryTree.levelForEach();

        System.out.println("======删除后：==========");

        binaryTree.remove(67);

        binaryTree.levelForEach();
    }




}
